package com.example.question.dp.dp1;

/**
 * @Date 2023-07-20
 * @Author Jonathan
 */
public class Code08_516 {


    public int longestPalindromeSubseq(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        if (s.length() == 1) {
            return 1;
        }
        char[] chars = s.toCharArray();
        int[][] dp = new int[s.length()][s.length()];
        for (int row = s.length(); row >= 0; row--) {
            for (int col = row; col < s.length(); col++) {
                if (row == col) {
                    // 对角线
                    dp[row][col] = 1;
                } else if (col == row + 1) {
                    if (chars[row] == chars[col]) {
                        dp[row][col] = 2;
                    } else {
                        dp[row][col] = 1;
                    }
                } else {
                    if (chars[row] == chars[col]) {
                        dp[row][col] = 2 + dp[row + 1][col - 1];
                    } else {
                        dp[row][col] = Math.max(dp[row + 1][col], dp[row][col - 1]);
                    }
                }

            }
        }
        return dp[0][chars.length - 1];
    }
}
